package link;

/**
 * 双向循环链表的操作
 */
public class CycleDoubleLinkList<T> {

    private Node head;
    private Node last;
    private int length;

    public CycleDoubleLinkList() {
        head = new Node(null, null, null);
        last = null;
        length = 0;
    }

    /**
     * 是否越界,index在长度内
     */
    private boolean isIndex(int index){
        return index >=0 && index < length;
    }

    /**
     * 是否越界
     */
    private boolean isPos(int index){
        return index >=0 && index <= length;
    }

    /**
     * 检测是否越界
     */
    private void checkIndex(int index){
        if (!isIndex(index)){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.length);
        }
    }

    /**
     * 检测是否越界
     */
    private void checkPos(int index){
        if (!isPos(index)){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.length);
        }
    }

    /**
     * 清空链表
     */
    public void clear(){
        head.next = null;
        last = null;
        length = 0;
    }

    /**
     * 判断链表是否为空，是返回true，否返回false
     */
    public boolean isEmpty(){
        return length == 0;
    }

    /**
     * 获取链表中元素的个数
     */
    public int length(){
        return length;
    }

    /**
     * 读取并返回链表中的第i个元素的值
     */
    public T get(int index){
        checkIndex(index);
        Node pause = head.next;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        return pause.data;
    }

    /**
     * 返回链表中首次出现的指定的数据元素的位序号
     */
    public int indexOf(T t){
        Node pause = head;
        for (int i=0;i<length;++i){
            pause = pause.next;
            if (pause.data == t){
                return i;
            }
        }
        return -1;
    }

    /**
     * 在链表中添加一个元素
     */
    public void add(T t){
        addLast(t);
    }

    /**
     * 添加尾节点
     */
    public void addLast(T t){
        Node pause = head;
        for (int i=0;i<length;++i){
            pause = pause.next;
        }
        last = new Node(pause, t, null);
        pause.next = last;
        ++length;
        cycleGo();
    }

    /**
     * 在链表的第i个元素之前插入一个值为t的数据元素
     */
    public void add(int index, T t){
        checkPos(index);
        if (index == length){
            addLast(t);
            return;
        }
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        Node newNode = new Node(pause, t, pause.next);
        pause.next.pre = newNode;
        pause.next = newNode;
        ++length;
        cycleGo();
    }

    /**
     * 第index个元素替换成一个值为t的数据元素
     */
    public void set(int index, T t){
        checkIndex(index);
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        pause.next.data = t;
    }

    /**
     * 删除并返回链表中第i个数据元素
     */
    public T remove(int index){
        checkIndex(index);
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        Node current = pause.next;
        if (current.next == null){
            pause.next = null;
        }else {
            current.next.pre = pause;
            pause.next = current.next;
        }
        --length;
        cycleGo();
        return current.data;
    }

    /**
     * 显示链表所有节点的数据
     */
    public String toString(){
        if (isEmpty()){
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        Node pause = head;
        for (int i=0;i<length;++i){
            pause = pause.next;
            if (!sb.toString().isEmpty()){
                sb.append(',').append(' ');
            }
            sb
                    .append("(")
                    .append(pause.pre==null || pause.pre.data==null ? null : pause.pre.data)
                    .append(",")
                    .append(pause.data)
                    .append(",")
                    .append(pause.next==null || pause.next.data==null ? null : pause.next.data)
                    .append(")");
        }
        sb
                .insert(0, "[")
                .append(']');
        return sb.toString();
    }

    /**
     * 形成环: 找到最后一个，将其next赋值为第一个
     */
    private void cycleGo(){
        last.next = head.next;
        head.next.pre = last;
    }

    /**
     * 获取第一个元素
     */
    public T getFirst(){
        return isEmpty()?null:head.next.data;
    }

    /**
     * 获取最后一个元素
     */
    public T getLast(){
        return last==null?null:last.data;
    }

    /**
     * 节点类
     */
    class Node {
        T data;
        Node next;
        Node pre;

        public Node(Node pre, T data, Node next) {
            this.data = data;
            this.next = next;
            this.pre = pre;
        }
    }
}
